package beauty.other;

import java.util.*;

/**
 *
 * Created by Robo on 2018/1/26.
 */
public class Maze {
    /**
     * Maze
     */
    private int width = 10, height = 10;
    //    private int width = 4 , height = 4;
    private Piece curr = null;
    private Piece prev = null;
    private List<Piece> processList = Collections.synchronizedList(new ArrayList<>());

    //障碍表
    int[][] block = {
            {0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
            {0, 1, 1, 0, 1, 1, 1, 0, 0, 0},
            {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
            {1, 1, 1, 0, 1, 0, 0, 0, 0, 0},
            {0, 1, 0, 0, 1, 0, 1, 1, 1, 0},
            {0, 1, 0, 0, 1, 1, 1, 1, 1, 0},
            {0, 0, 0, 1, 1, 0, 0, 0, 1, 0},
            {0, 1, 0, 0, 0, 0, 1, 0, 1, 0},
            {0, 1, 1, 1, 0, 1, 1, 0, 1, 1},
            {0, 0, 0, 0, 0, 0, 1, 0, 0, 0},
    };

    /*  int[][] block = {
              {0, 1, 0, 1},
              {0, 0, 0, 1},
              {0, 1, 0, 0},
              {1, 1, 1, 0},
      };
  */
    class Piece {
        int x = 0, y = 0;

        public Piece() {
        }

        public Piece(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public Piece(Piece p) {
            this.x = p.x;
            this.y = p.y;
        }

        public Piece move(Direction dir) {
            Piece p = new Piece(this);
            switch (dir) {
                case up:
                    if (y > 0 && canMove(x, y - 1)) {
                        p.y--;
                    }
                    break;
                case down:
                    if (y < height - 1 && canMove(x, y + 1)) {
                        p.y++;
                    }
                    break;
                case left:
                    if (x > 0 && canMove(x - 1, y)) {
                        p.x--;
                    }
                    break;
                case right:
                    if (x < width - 1 && canMove(x + 1, y)) {
                        p.x++;
                    }
                    break;
                default:
                    System.out.println(x + " " + y + " can't move");
                    return null;
//                    throw new RuntimeException(x+" "+y+" can't move");
            }
            return p;
        }

        @Override
        public String toString() {
            return "Piece{" +
                    "x=" + x +
                    ", y=" + y +
                    '}';
        }
    }


    enum Direction {
        left, right, up, down,
    }


    Boolean canMove(int x, int y) {
        return block[y][x] == 0;
    }

    Set<Integer> prevMoveSet = new HashSet<>();

    Boolean prevMove(int x, int y) {
        return prevMoveSet.contains(x + 10 * y);
    }

    Boolean finished(Piece piece) {
        return piece.x == this.width - 1 && piece.y == height - 1;
    }

    public static void main(String[] args) {
        Maze maze = new Maze();
        maze.curr = maze.new Piece();
        int step = 0;
        maze.processList.add(maze.processList.size(), maze.curr);
        runDfs(maze, step, maze.curr);

        maze = new Maze();
        maze.curr = maze.new Piece();
        runBfs(maze,maze.curr);
//        System.out.println(maze.processList.subList(0, step + 1));

    }

    private static void runDfs(Maze maze, int step, Piece curr) {
        List<Piece> processList = maze.processList;
        for (Direction dir : Direction.values()) {
            if (step > 1) {
                curr = processList.get(step);//prev
            }
            if (step > 1000) {
                System.out.println("too many...");
                break;
            }
            maze.prevMoveSet.add(10 * curr.y + curr.x);
            maze.prev = maze.new Piece(curr);
            curr = curr.move(dir);
            if (null != curr && !maze.prevMove(curr.x, curr.y)) {
                step++;
                if (maze.finished(curr)) {
                    System.out.println("congratulation~ step:" + step);
                    break;
                } else {
                    System.out.println("step:" + step + " dir:" + dir.name()
                            + " px:" + maze.prev.x + maze.prev.y
                            + " x:" + curr.x + curr.y);
                    processList.add(step, maze.new Piece(curr));
//                    maze.curr = next;
                    runDfs(maze, step, curr);
                    step--;//就是漏了这个....
                }
            } else {
                curr = maze.prev;
            }
        }
    }

    private List<Trajectory> trajectoryList = new ArrayList<>();
    //    记录轨迹
    class Trajectory {
        List<Piece> list = new ArrayList<>();
        public Trajectory(){
        }

        public Trajectory(Piece piece) {
            list.add(new Piece());
        }

        public Trajectory addPiece( Piece piece) {
            Trajectory result = new Trajectory();
            result.list.addAll(this.list);
            result.list.add(piece);
            return result;
        }
        public Piece getCurr() {
            return list.get(list.size() - 1);
        }

        @Override
        public String toString() {
            return "Trajectory{" +
                    "list=" + list +
                    '}';
        }
    }

    private static void runBfs(Maze maze, Piece curr) {
        int step = 0;
        Trajectory first = maze.new Trajectory(maze.new Piece());

        maze.trajectoryList.add(first);
        while (true) {
            List<Trajectory> temp = new ArrayList<>();
            temp.addAll(maze.trajectoryList);
            maze.trajectoryList.clear();
            // 所有路线
            for (int i = 0; i < temp.size(); i++) {
                Trajectory trajectory = temp.get(i);
                curr = trajectory.getCurr();//1粒棋
                for (Direction dir : Direction.values()) {
                    maze.prevMoveSet.add(10 * curr.y + curr.x);
                    Piece moved = curr.move(dir);
                    if (null != moved && !maze.prevMove(moved.x, moved.y)) {
                        maze.trajectoryList.add(trajectory.addPiece(moved));
                        if (maze.finished(moved)) {
                            step++;
                            System.out.println("congratulation~ Bfs");
                            System.out.println("step:"+step + " List: " +maze.trajectoryList);
                            return;
                        }
                    }
                }
            }
            step++;
            System.out.println("step:"+step + " List: " +maze.trajectoryList);
            if (maze.trajectoryList.size() == 0) {
                System.out.println("mission failed....");
                break;
            }
        }

    }
}